package 算法.NiuKe.JZ;

import java.util.*;
/**
 * @author:谢君臣
 * @Date:2021/3/248:15
 * @version:1.0
 * @function:
 */
public class JZ27 {
    public static void main(String[] args) {
        Permutation("add");
    }
    public static ArrayList<String> Permutation(String str) {
        HashSet<String> hashSet = new HashSet<>();
        Stack<String> stack = new Stack<>();
        char[] chars = str.toCharArray();
        for (char c : chars) {
            stack.add(String.valueOf(c));
        }
        while (!stack.isEmpty()){
            String s = stack.pop();
            if (hashSet.isEmpty()){   //如果是第一个元素，直接添加
                hashSet.add(s);
            }else {
                HashSet<String> hash = new HashSet<>();
                for (String string : hashSet) { // 遍历现有的长度构建的字串
                    for (int i = 0; i <= string.length(); i++) {  // 在已有的串中添加一个新元素
                        String stringBuilder = string.substring(0,i)+s+string.substring(i);
                        hash.add(stringBuilder); // 将结果放在hash表中，这一步可以去掉重复发情况
                    }
                }
                hashSet = (HashSet<String>)hash.clone(); // 将结果clone 到原始的hash表中，继续添加后面的元素
            }
        }
        ArrayList<String> res = new ArrayList<>(hashSet);
        res.sort(String::compareTo);

        // LeetCode 的返回结果
//        String[]re = new String[hashSet.size()];
//        hashSet.toArray(re);
        return res;
    }
}
